package lc20240605;

import lc20240604.EvaluateDivision;

import java.util.*;

public class Division {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries){
        //构建图
        Map<String,Map<String,Double>> graph=new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String A=equations.get(i).get(0);
            String B=equations.get(i).get(1);

            double val=values[i];

            graph.putIfAbsent(A,new HashMap<>());
            graph.putIfAbsent(B,new HashMap<>());

            graph.get(A).put(B,val);
            graph.get(B).put(A,1.0/val);
        }


        double[] res=new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String C=queries.get(i).get(0);
            String D=queries.get(i).get(1);

            if (!graph.containsKey(C)||!graph.containsKey(D)){
                res[i]=-1.0;
            }else if (C.equals(D)){
                res[i]=1.0;
            }else {
                Set<String> visited=new HashSet<>();
                res[i]=dfs(graph,C,D,visited);
            }
        }

        return res;
    }

    private double dfs(Map<String, Map<String, Double>> graph, String c, String d, Set<String> visited) {
        if (graph.get(c).containsKey(d)){
            return graph.get(c).get(d);
        }
        visited.add(c);
        for (Map.Entry<String, Double> entry : graph.get(c).entrySet()) {
            String neigh=entry.getKey();
            if (visited.contains(neigh)){
                continue;
            }
            double intermediateResult=dfs(graph,neigh,d,visited);
            if (intermediateResult!=-1.0){
                return entry.getValue()*intermediateResult;
            }
        }
        return -1.0;
    }

    public static void main(String[] args) {
        EvaluateDivision solver = new EvaluateDivision();

        List<List<String>> equations = Arrays.asList(
                Arrays.asList("a", "b"),
                Arrays.asList("b", "c")
        );
        double[] values = {2.0, 3.0};
        List<List<String>> queries = Arrays.asList(
                Arrays.asList("a", "c"),
                Arrays.asList("b", "a"),
                Arrays.asList("a", "e"),
                Arrays.asList("a", "a"),
                Arrays.asList("x", "x")
        );

        System.out.println(Arrays.toString(solver.calcEquation(equations, values, queries)));
    }
}
